Couple de Bézout pour 189 et 255 - Corrigé

Énoncé

À l'aide de l'algorithme d'Euclide, déterminer le PGCD de  \(189\)  et  \(255\) , ainsi que deux entiers relatifs \(u\) et \(v\) tels que \(189u+255v=\mathrm{PGCD}(189;255)\) .

Solution

On applique l'algorithme d'Euclide pour \(255\) et \(189\) :

\(\begin{align*}\renewcommand{\arraystretch}{1.2}\begin{array}{|c|c|c|c|}\hline a&b&q&r\\ \hline 255&189&1&66\\ \hline 189&66&2&57\\ \hline 66&57&1&9\\ \hline 57&9&6&3\\ \hline 9&3&3&0 \\ \hline \end{array} \begin{array}{ll}\ & \\ \times (-20)& \text{suppression du reste } 66 \\ \times 7& \text{suppression du reste } 57\\ \times (-6)& \text{suppression du reste } 9\\ \times 1& \text{conservation du PGCD}\\ & \end{array}\end{align*}\)   

On en déduit que  \(\mathrm{PGCD}(189;255)=3\) .

En additionnant les lignes après avoir éliminé les restes intermédiaires, on obtient :
\(\begin{align*}255 \times (-20)+189 \times 7=189 \times 1 \times (-20)+3 & \ \ \Longleftrightarrow \ \ 189 \times 27+255 \times (-20)=3\end{align*}\)
donc le couple \((u;v)=(27;-20)\) convient.